/*
* leetcode 面试题 17.19. 消失的两个数字
*
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。
你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
示例 1:

输入: [1]
输出: [2,3]
示例 2:

输入: [2,3]
输出: [1,4]
* */
/*
思路:
先将所有元素异或一遍，得到缺失的两个数字的异或值ret
根据ret最左边的1所在位置将数组分为两个部分
分类后再异或就能得到其中一个元素的值
拿ret与其异或，就能得到另一个值
* */
import java.util.*;
class Solution {
    public int[] missingTwo(int[] nums) {
        int n=nums.length;
        int[] ans=new int[2];
        int ret=0;
        for(int i=0;i<n;i++){
            ret^=nums[i];
        }
        for(int i=1;i<=n+2;i++){
            ret^=i;
        }
        int rightOne=0;
        while(true){
            if(((ret>>rightOne)&1)==1)break;
            else rightOne++;
        }
        for(int i=0;i<n;i++){
            if(((nums[i]>>rightOne)&1)==1)ans[0]^=nums[i];
        }
        for(int i=1;i<=n+2;i++){
            if(((i>>rightOne)&1)==1)ans[0]^=i;
        }
        ans[1]=ret^ans[0];
        return ans;
    }
}